package com.data.practice.linkedlist;

import java.util.Stack;

public class SingleLinkedListDemo {

	public static void main(String[] args) {

		HeroNode hero1 = new HeroNode(1, "?ν?", "?????");
		HeroNode hero2 = new HeroNode(2, "?????", "??????");
		HeroNode hero3 = new HeroNode(3, "????", "?????");
		HeroNode hero4 = new HeroNode(4, "???", "?????");
		
		//???????????
		SingleLinkedList singleLinkedList = new SingleLinkedList();
		
		
		//????
		singleLinkedList.add(hero1);
		singleLinkedList.add(hero4);
		singleLinkedList.add(hero2);
		singleLinkedList.add(hero3);

		// ???????????????????
		System.out.println("???????????~~");
		singleLinkedList.list();
		
//		System.out.println("?????????~~");
//		reversetList(singleLinkedList.getHead());
//		singleLinkedList.list();
		
		System.out.println("????????????????, ??и????????~~");
		reversePrint(singleLinkedList.getHead());
		
/*		
		//????????????
		singleLinkedList.addByOrder(hero1);
		singleLinkedList.addByOrder(hero4);
		singleLinkedList.addByOrder(hero2);
		singleLinkedList.addByOrder(hero3);
		
		//??????
		singleLinkedList.list();
		
		//?????????????
		HeroNode newHeroNode = new HeroNode(2, "С?", "??????~~");
		singleLinkedList.update(newHeroNode);
		
		System.out.println("????????????~~");
		singleLinkedList.list();
		
		//?????????
		singleLinkedList.del(1);
		singleLinkedList.del(4);
		System.out.println("?????????????~~");
		singleLinkedList.list();
		
		//??????? ??????????Ч???????
		System.out.println("??Ч???????=" + getLength(singleLinkedList.getHead()));//2
		
		//??????????????????????K?????
		HeroNode res = findLastIndexNode(singleLinkedList.getHead(), 3);
		System.out.println("res=" + res);
*/		
		
	}
	
	//???2??
	//?????????????????????????????????У?????????????????????????????????????Ч??
	public static void reversePrint(HeroNode head) {
		if(head.next == null) {
			return;//????????????
		}
		//??????????????????????????
		Stack<HeroNode> stack = new Stack<HeroNode>();
		HeroNode cur = head.next;
		//??????????н??????
		while(cur != null) {
			stack.push(cur);
			cur = cur.next; //cur?????????????????????????
		}
		//????е?????д??,pop ???
		while (stack.size() > 0) {
			System.out.println(stack.pop()); //stack?????????????
		}
	}
	
	//?????????
	public static void reversetList(HeroNode head) {
		//??????????????????????????????跴?????????
		if(head.next == null || head.next.next == null) {
			return ;
		}
		
		//????????????????(????)??????????????????????
		HeroNode cur = head.next;
		HeroNode next = null;// ???????[cur]??????????
		HeroNode reverseHead = new HeroNode(0, "", "");
		//???????????????????????????????????????????????reverseHead ???????
		//?????
		while(cur != null) { 
			next = cur.next;//????????浱??????????????????????????
			cur.next = reverseHead.next;//??cur??????????????????????????
			reverseHead.next = cur; //??cur ??????????????
			cur = next;//??cur????
		}
		//??head.next ??? reverseHead.next , ???????????
		head.next = reverseHead.next;
	}
	
	//??????????е??????k????? ????????????
	//?·
	//1. ??д?????????????head????????????index 
	//2. index ??????????index?????
	//3. ???????????β???????????????????? getLength
	//4. ???size ??????????????????????? (size-index)???????????
	//5. ????????????????????nulll
	public static HeroNode findLastIndexNode(HeroNode head, int index) {
		//?ж????????????????null
		if(head.next == null) {
			return null;//??????
		}
		//????????????????????(??????)
		int size = getLength(head);
		//????α???  size-index λ?????????????????K?????
		//???????index??У??
		if(index <=0 || index > size) {
			return null; 
		}
		//??????????????? for ?????λ????????index
		HeroNode cur = head.next; //3 // 3 - 1 = 2
		for(int i =0; i< size - index; i++) {
			cur = cur.next;
		}
		return cur;
		
	}
	
	//????????????????????????(??????????????????????????)
	/**
	 * 
	 * @param head ?????????
	 * @return ??????????Ч???????
	 */
	public static int getLength(HeroNode head) {
		if(head.next == null) { //??????
			return 0;
		}
		int length = 0;
		//????????????????, ??????????????????
		HeroNode cur = head.next;
		while(cur != null) {
			length++;
			cur = cur.next; //????
		}
		return length;
	}

}


//定义SingleLinkedList 来管理我们的英雄
class SingleLinkedList {
	//先初始化头节点
	private HeroNode head = new HeroNode(0, "", "");

	//
	public HeroNode getHead() {
		return head;
	}

	//添加节点到单向列表
	//思路 ： 找到当前链表的最后节点
	//       将最后这个节点的next指向新的节点
	public void add(HeroNode heroNode) {
		
		//定义一个临时节点指向头节点
		HeroNode temp = head;
		//遍历到最后一个节点
		while(true) {
			//找到链表的最后
			if(temp.next == null) {//
				break;
			}
			//后移一位
			temp = temp.next;
		}
		//temp指向了列表的最后
		//将新节点指向最后一个节点
		temp.next = heroNode;
	}
	
	//?????????????????????????????????????λ??
	//(????????????????????????????????)
	public void addByOrder(HeroNode heroNode) {
		//???????????????????????????????????(????)?????????????λ??
		//???????????????????temp ??λ?? ???λ???????????????????
		HeroNode temp = head;
		boolean flag = false; // flag????????????????????false
		while(true) {
			if(temp.next == null) {//???temp?????????????
				break; //
			} 
			if(temp.next.no > heroNode.no) { //λ???????????temp????????
				break;
			} else if (temp.next.no == heroNode.no) {//??????????heroNode???????????
				
				flag = true; //?????????
				break;
			}
			temp = temp.next; //????????????????
		}
		//?ж?flag ???
		if(flag) { //?????????????????
			System.out.printf("?????????????? %d ?????????, ???????\n", heroNode.no);
		} else {
			//??????????, temp?????
			heroNode.next = temp.next;
			temp.next = heroNode;
		}
	}

	//?????????, ????no???????????no???????.
	//???
	//1. ???? newHeroNode ?? no ????????
	public void update(HeroNode newHeroNode) {
		//?ж?????
		if(head.next == null) {
			System.out.println("???????~");
			return;
		}
		//????????????, ????no???
		//???????????????
		HeroNode temp = head.next;
		boolean flag = false; //?????????????
		while(true) {
			if (temp == null) {
				break; //?????????????
			}
			if(temp.no == newHeroNode.no) {
				//???
				flag = true;
				break;
			}
			temp = temp.next;
		}
		//????flag ?ж??????????????
		if(flag) {
			temp.name = newHeroNode.name;
			temp.nickname = newHeroNode.nickname;
		} else { //??????
			System.out.printf("?????? ??? %d ???????????\n", newHeroNode.no);
		}
	}
	
	//??????
	//?·
	//1. head ????????????????????temp??????????????????????????
	//2. ????????????????temp.next.no ??  ???????????no???
	public void del(int no) {
		HeroNode temp = head;
		boolean flag = false; // ??????????????????
		while(true) {
			if(temp.next == null) { //?????????????
				break;
			}
			if(temp.next.no == no) {
				//????????????????????temp
				flag = true;
				break;
			}
			temp = temp.next; //temp?????????
		}
		//?ж?flag
		if(flag) { //???
			//???????
			temp.next = temp.next.next;
		}else {
			System.out.printf("?????? %d ???????\n", no);
		}
	}
	
	//显示链表
	public void list() {
		//判断列表为空
		if(head.next == null) {
			System.out.println("链表为空");
			return;
		}
		//因为头节点一直不能动 需要一个辅助变量来进行遍历
		HeroNode temp = head.next;
		while(true) {
			//temp指向null
			if(temp == null) {
				break;
			}

			System.out.println(temp);
			//后移一位
			temp = temp.next;
		}
	}
}

//定义HeroNode  每个HeroNode 对象就是一个节点
class HeroNode {
	public int no;   // 编号
	public String name;  //名字
	public String nickname;  //昵称
	public HeroNode next; //指向下一个节点
	//构造器 -- 创建一个英雄
	public HeroNode(int no, String name, String nickname) {
		this.no = no;
		this.name = name;
		this.nickname = nickname;
	}
    //重写toString
	@Override
	public String toString() {
		return "HeroNode{" +
				"no=" + no +
				", name='" + name + '\'' +
				", nickname='" + nickname + '\'' +
				", next=" + next +
				'}';
	}
}
